package hill_sort

import (
	"common"
)

func Sort1(arr []int) {
	N := len(arr)
	h := 1
	for h < N/3 {
		h = 3*h + 1
	}
	for h >= 1 {
		for i := h; i < N; i++ {
			for j := i; j >= h && arr[j] < arr[j-h]; j -= h {
				common.Exch(arr, j, j-h)
			}
		}
		h = h / 3
	}
}

